// https://leetcode.cn/problems/sort-an-array/

// 算法思路总结：
// 1. 三路快速排序算法实现数组排序
// 2. 随机选择基准值key，避免最坏情况
// 3. 三路分区：小于key | 等于key | 大于key
// 4. 递归排序小于区和大于区，等于区已有序
// 5. 时间复杂度：O(nlogn)，空间复杂度：O(logn)

#include <iostream>
using namespace std;

#include <ctime>
#include <vector>
#include <cstdlib>
#include <algorithm>

class Solution 
{
public:
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }

    void qsort(vector<int>& nums, int left, int right)
    {
        if (left >= right)
        {
            return ;
        }

        int key = getRandom(nums, left, right);
        int begin = left - 1, end = right + 1, cur = left;
        while (cur < end)
        {
            if (nums[cur] < key)
            {
                swap(nums[++begin], nums[cur++]);
            }
            else if (nums[cur] == key)
            {
                cur++;
            }
            else if (nums[cur] > key)
            {
                swap(nums[--end], nums[cur]);
            }
        }

        qsort(nums, left, begin);
        qsort(nums, end, right);
    }

    vector<int> sortArray(vector<int>& nums) 
    {
        srand((unsigned)time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};

int main()
{
    vector<int> nums1 = {5,2,3,1}, nums2 = {5,1,1,2,0,0};
    Solution sol;

    sol.sortArray(nums1);
    sol.sortArray(nums2);

    for (const int& num : nums1)
        cout << num << " ";
    cout << endl;

    for (const int& num : nums2)
        cout << num << " ";
    cout << endl;

    return 0;
}